public class _8minWindow {
    //最小覆盖子串
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        int[] hash1 = new int[128];
        int kinds = 0;
        for(char ch: t)
            if(hash1[ch]++ == 0) kinds++;//记录t中的种类数

        int[] hash2 = new int[128];
        int begin = -1,minlen = Integer.MAX_VALUE;
        for(int left=0,right=0,count=0;right < s.length;right++){
            //进窗口
            char in = s[right];
            if(++hash2[in] == hash1[in]) count++;
            //判断
            while(count >= kinds){
                //更新结果
                if(minlen > right - left +1){
                    begin = left;
                    minlen = right - left +1;
                }
                //出窗口
                char out = s[left++];
                if(hash2[out]-- == hash1[out]) count--;
            }
        }
        if(begin != -1) return ss.substring(begin,begin+minlen);
        else return new String();
    }
}
